package main

func findTarget(root *TreeNode, k int) bool {
	if nil == root {
		return false
	}
	maps := make(map[int]int)
	queue := []*TreeNode{}
	queue = append(queue, root)
	for len(queue) > 0 {
		l := len(queue)
		for i := 0; i < l; i++ {
			v := queue[0]
			queue = queue[1:]
			if _, exist := maps[k-v.Val]; exist {
				return true
			}
			maps[root.Val] = v.Val
			if nil != v.Left {
				queue = append(queue, v.Left)
			}
			if nil != v.Right {
				queue = append(queue, v.Right)
			}
		}
	}
	return false
}
